
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        int m = 0; // 记录负数个数
        int ret = 0;
        for (auto &ch : nums)
        {
            if (ch < 0)
                m++;
        }
        if (m >= k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++)
            {
                nums[i] = -nums[i];
            }
            for (int i = 0; i < nums.size(); i++)
            {
                ret += nums[i];
            }
            return ret;
        }
        else
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < m; i++)
            {
                nums[i] = -nums[i];
            }
            for (int i = 0; i < nums.size(); i++)
            {
                ret += nums[i];
            }
            if ((k - m) % 2 == 0)
            {
                return ret;
            }
            else
            {
                sort(nums.begin(), nums.end());
                ret -= 2 * nums[0];
                return ret;
            }
        }
    }
};